In practice, most mechanisms for selling, buying, matching, voting, and so on are not incentive compatible: agents can improve their utilities by bidding strategically. We show how to estimate the extent to which an agent can improve his utility by bidding strategically, given samples from the distribution over agents' values. We do so by first measuring the maximum utility an agent can gain by misreporting his value on average over the samples, assuming his true and reported values are from a finite subset of the value space. The primary challenge is proving that the maximum utility gain over this finite subset nearly matches the maximum utility gain overall, despite the volatility of the utility functions we study. We apply our tools to several well-studied mechanisms, including the first-price and generalized second-price auctions.

This is joint work with Nina Balcan and Tuomas Sandholm.